//
// Created by Administrator on 2023/11/21.
//

//Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;

    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    void rearrangedList(ListNode *head) {
        //只有一个元素直接返回
        if (head->next == nullptr) return;

        //获得长度
        int len = 0;
        for (auto p = head; p; p = p->next)
            len++;

        //找到中间位置，上取整，使前半部分更长
        int mid = (len + 1) / 2;

        //将前后分成两端
        //找到前端最后一个结点
        auto a = head;
        for (int i = 0; i < mid - 1; ++i) {
            a = a->next;
        }
        //将后一段取反 b结束之后指向了头部
        auto b = a->next, c = b->next;
        b->next = nullptr;
        while(c){
            auto x=c->next;
            c->next=b;
            b=c;
            c=x;
        }

        a->next= nullptr;//分离前后两端

        //合并
        auto p=head,q=b;
        while(q){
            auto x=q->next;
            q->next=p->next;
            p->next=q;

            p=q->next;
            q=x;
        }
    }
};